Skip to main content

第54章 二叉树的搜索算法

二叉树的搜索算法是指在二叉树中查找满足特定条件的节点（如查找指定值、符合条件的路径等）的方法。由于二叉树属于非线性结构，搜索策略和数组、链表存在明显区别，需要结合遍历方式设计查找逻辑。

54.1 二叉树搜索的基本概念​

54.1.1 搜索目标​

  1. 查找包含特定值的节点
  2. 查找叶子节点、最大值节点、最小值节点等满足特定属性的节点
  3. 查找从根节点到目标节点的完整路径
  4. 查找所有根到叶子、节点值之和等于目标的路径

54.1.2 搜索策略分类​

  1. 深度优先搜索（DFS）：包含前序、中序、后序遍历，适合需要深入遍历深层节点的场景
  2. 广度优先搜索（BFS，层次遍历）：按层级依次访问，适合优先查找浅层目标节点

54.2 按值搜索算法​

54.2.1 深度优先（递归）实现​

二叉树节点基础定义：

#include <iostream>
using namespace std;
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode (int x): val(x), left (NULL), right (NULL) {}
};

前序搜索：根 → 左 → 右​

TreeNode* preorderSearch (TreeNode *root, int target) {
    if (root == NULL){
        return NULL;
    }
    if (root->val == target){
        return root;
    }
    TreeNode *leftResult = preorderSearch (root->left, target);
    if (leftResult!= NULL){
        return leftResult;
    }
    return preorderSearch (root->right, target);
}

中序搜索：左 → 根 → 右​

TreeNode* inorderSearch (TreeNode *root, int target) {
    if (root == NULL){
        return NULL;
    }
    TreeNode *leftResult = inorderSearch (root->left, target);
    if (leftResult != NULL){
        return leftResult;
    }
    if (root->val == target){
        return root;
    }
    return inorderSearch (root->right, target);
}

后序搜索：左 → 右 → 根​

TreeNode* postorderSearch (TreeNode *root, int target) {
    if (root == NULL){
        return NULL;
    }
    TreeNode *leftResult = postorderSearch (root->left, target);
    if (leftResult != NULL){
        return leftResult;
    }
    TreeNode *rightResult = postorderSearch (root->right, target);
    if (rightResult != NULL){
        return rightResult;
    }
    if (root->val == target){
        return root;
    }
    return NULL;
}

说明：三种深度优先搜索仅访问节点的时机不同；普通无序二叉树三者效率一致；二叉排序树可利用有序性优化中序搜索。

54.2.2 广度优先（层次）实现​

#include <queue>
using namespace std;
TreeNode* levelorderSearch (TreeNode *root, int target) {
    if (root == NULL){
        return NULL;
    }
    queue<TreeNode*> q;
    q.push (root);
    while (!q.empty()){
        TreeNode *node = q.front();
        q.pop();
        if (node->val == target){
            return node;
        }
        if (node->left != NULL){
            q.push (node);
        }
        if (node->right != NULL){
            q.push (node->right);
        }
    }
    return NULL;
}

优势：目标节点处于浅层时，无需遍历深层分支，查找速度更快。

54.3 按条件搜索算法​

54.3.1 查找所有叶子节点​

#include <vector>
using namespace std;
void findLeaves (TreeNode *root, vector<TreeNode*>& leaves){
    if (root == NULL){
        return;
    }
    if (root->left == NULL && root->right == NULL) {
        leaves.push_back (root);
        return;
    }
    findLeaves (root->left, leaves);
    findLeaves (root->right, leaves);
}

54.3.2 查找最大值节点（递归）​

TreeNode* findMax (TreeNode *root) {
    if (root == NULL){
        return NULL;
    }
    TreeNode *leftMax = findMax(root->left);
    TreeNode *rightMax = findMax(root->right);
    TreeNode *maxNode = root;
    if (leftMax != NULL && leftMax->val > maxNode->val)
        maxNode = leftMax;
    if (rightMax != NULL && rightMax->val > maxNode->val)
        maxNode = rightMax;
    return maxNode;
}

54.3.3 查找最小值节点（层次遍历）​

TreeNode* findMin (TreeNode *root) {
    if (root == NULL){
        return NULL;
    }
    TreeNode *minNode = root;
    queue<TreeNode*> q;
    q.push (root);
    while (!q.empty()){
        TreeNode *node = q.front();
        q.pop();
        if (node->val < minNode->val){
            minNode = node;
        }
        if(node->left!= NULL){
            q.push (node->left);
        }
        if (node->right != NULL) {
            q.push (node->right);
        }
    }
    return minNode;
}

54.3.4 查找指定深度k的所有节点​

void findNodesAtDepth (TreeNode *root, int k, vector<TreeNode*>& result) {
    if (root == NULL || k<1){
        return;
    }
    queue<TreeNode*> q;
    q.push (root);
    int currentDepth=1;
    while (!q.empty()){
        int levelSize = q.size();
        if (currentDepth == k){
            for (int i =0; i<levelSize; i++) {
                result.push_back(q.front());
                q.pop();
            }
            return;
        }
        for (int i=0;i<levelSize; i++) {
            TreeNode *node = q.front();
            q.pop();
            if (node->left!= NULL){
                q.push (node->left);
            }
            if (node->right != NULL){
                q.push (node->right);
            }
        }
        currentDepth++;
    }
}

54.4 路径搜索算法​

54.4.1 回溯查找根到目标节点路径​

bool findPathToTarget(TreeNode *root, int target, vector<TreeNode*> path) {
    if(root == NULL){
        return false;
    }
    path.push_back (root);
    if (root->val == target) {
        return true;
    }
    bool leftFound = findPathToTarget (root->left, target, path);
    if(leftFound){
        return true;
    }
    bool rightFound = findPathToTarget (root->right, target);
    if(rightFound){
        return true;
    }
    path.pop_back();
    return false;
}

54.4.2 查找根到叶子、和为目标的全部路径​

void findPathsWithSum(TreeNode *root, int target, int currentSum, vector<int>& currentPath, vector<vector<int>>& result){
    if (root == NULL){
        return;
    }
    currentSum += root->val;
    currentPath.push_back (root->val);
    if (root->left == NULL && root->right == NULL && currentSum == target)
    {
        result.push_back (currentPath);
    } else{
        findPathsWithSum (root->left, target, currentSum, currentPath, result);
        findPathsWithSum (root->right, target, currentSum, currentPath, result);
    }
    currentPath.pop_back();
}

//对外调用接口
vector<vector<int>> getPathsWithSum(TreeNode *root, int target){
    vector<vector<int>> result;
    vector<int> currentPath;
    findPathsWithSum(root, target, 0, currentPath, result);
    return result;
}

54.5 二叉排序树高效搜索​

54.5.1 BST非递归查找实现​

TreeNode* bstSearch (TreeNode *root, int target) {
    TreeNode *current = root;
    while (current != NULL) {
        if (current->val == target){
            return current;
        } else if (target < current->val){
            current=current->left;
        }else{
            current=current->right;
        }
    }
    return NULL;
}

54.5.2 优势分析​

普通无序二叉树最坏需要遍历全部节点，时间复杂度O(n)O(n)； 平衡二叉排序树每次排除一半分支，时间复杂度O(log⁡n)O(\log n)。

54.6 搜索算法的优化策略​

剪枝优化示例（路径求和提前终止无效分支）​

void findPathsWithSumPruned (TreeNode *root, int target, int currentSum, vector<int>& path, vector<vector<int>>& result) {
    if(root== NULL || currentSum>target){
        return;
    }
    //后续遍历逻辑与原版保持一致
}
  1. 剪枝：路径求和场景，当前累加值已超过目标则直接终止该分支递归
  2. 缓存：频繁查询最大/最小值时，缓存结果避免重复全树遍历
  3. 遍历选择
    • 浅层目标优先BFS层次遍历
    • 需要遍历全树使用DFS
    • BST必须使用专用有序查找逻辑

54.7 注意事项​

  1. 空树处理：所有遍历、查找函数开头必须判断root == NULL，防止空指针异常
  2. 回溯正确性：路径记录类递归，递归返回前必须pop弹出当前节点，避免路径冗余
  3. 重复值处理：树存在重复节点值时，区分「找到第一个匹配节点」「收集所有匹配节点」两种需求
  4. 复杂度总结
    • 普通二叉树全量搜索：O(n)O(n)
    • 平衡二叉排序单次查找：O(log⁡n)O(\log n)
    • 退化斜BST最坏查找：O(n)O(n)